package org.example.algorithm.binarytree;

import org.example.algorithm.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

public class HasPathSumSolution {
    public static void main(String[] args) {

    }

    //DFS递归
    boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null && root.val == targetSum) {
            return true;
        }
        return hasPathSum(root.left, targetSum - root.val)
                || hasPathSum(root.right, targetSum - root.val);
    }

    //BFS
    public boolean hasPathSum2(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        Queue<TreeNode> treeNodeQueue = new LinkedList<>();
        Queue<Integer> sumQueue = new LinkedList<>();
        treeNodeQueue.offer(root);
        sumQueue.offer(root.val);
        while (!treeNodeQueue.isEmpty()) {
            TreeNode curNode = treeNodeQueue.poll();
            Integer curSum = sumQueue.poll();
            if (curNode.left == null && curNode.right == null && curSum == targetSum) {
                return true;
            }
            if (curNode.left != null) {
                treeNodeQueue.offer(curNode.left);
                sumQueue.offer(curSum + curNode.left.val);
            }
            if (curNode.right != null) {
                treeNodeQueue.offer(curNode.right);
                sumQueue.offer(curSum + curNode.right.val);
            }
        }
        return false;
    }
}
